﻿#include"Heap.h"


//1、需要堆的数据结构
//2、空间复杂度 O(N)
void test1() //  用堆排序   提供堆的数据结构   
//   所以用提供数组初始化堆实现堆排序
{
	int arr[] = { 19 ,29 ,20 ,16 ,88 };
	int n = sizeof(arr) / sizeof(arr[0]);
	HP hp;
	HPInit(&hp);
	for (int i = 0; i < n; i++)
	{
		HPPush(&hp, arr[i]);
	}
	int i = 0;
	while (!HPEmpty(&hp))
	{
		arr[i++] = HPTop(&hp);
		HPPop(&hp);
	}
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << ' ';
	}
	HPDestory(&hp);
}

void test()
{
	HP hp;
	HPInit(&hp);
	HPPush(&hp, 9);
	HPPush(&hp, 4);
	HPPush(&hp, 8);
	HPPush(&hp, 7);

	while (!HPEmpty(&hp))
	{
		cout << HPTop(&hp) << ' ';
		HPPop(&hp);
	}
	HPDestory(&hp);
}

// 升序，建⼤堆   
// 降序，建⼩堆
// O(N*logN)
void HeapSort(int* a, int n)
{
	// a数组直接建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)  //  选择倒数第二层的结点，恰好有孩子结点 
	{									//  因为n带边元素个数，所以n需要减1，然后根据孩子和父亲结点的推断 
		AdjustDown(a, i, n);    			// i从（n-1-1）/2 开始 依次往上走 然后依次向下调整堆   
	}										//  遍历到堆顶时，堆就建好了
	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		swap(a[0], a[end]);  //  每次更换堆顶与最后一个元素，再重新向下调整 
		AdjustDown(a, 0, end);
		--end;
	}
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << ' ';   //  使用堆排好序之后，直接打印就好啦  
	}
}

int main()
{

	test();

	return 0;
}